package com.shm.leetcode;

/**
 * 42. 接雨水
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 *
 *
 *
 * 示例 1：
 *
 *
 *
 * 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
 * 输出：6
 * 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
 * 示例 2：
 *
 * 输入：height = [4,2,0,3,2,5]
 * 输出：9
 *
 *
 * 提示：
 *
 * n == height.length
 * 0 <= n <= 3 * 104
 * 0 <= height[i] <= 105
 * @author SHM
 */
public class Trap {
    /**
     * 方法三：双指针
     * 思路分析：
     *
     * 由暴力解法知道，一个位置的能储存雨水的格子数和两侧有关；
     * 有些位置只和一侧有关，那就是位置 1 和位置 len - 1 。位置 1 由于在最左边，只需要扫右侧，len - 2 由于在最右边只需要扫左侧；
     * 利用木桶原理，连扫描的步骤都可以省了，我们来看下面两种情况：
     *
     *
     * 情况 1：左边已经看到的最高高度 < 右边已经看到的最高高度。
     *
     * 左边和右边已经看到的最高高度只有 11 个，此时右边虽然还没有扫描，但是下标位置 11 的存水量是可以确定的。它等于：左边已经看到的最高高度 - 当前自己的柱子的高度（大于 00 时有效）。
     *
     * 因为即使中间还有一大片没有扫，根据木桶原理，有最右边的柱子存在，中间的柱子或者达到最高，或者中间的柱子都不存在，都不会影响到位置 11 的存水量。
     *
     * 接下来，由于位置 11 确定了，可以把 left 向左移动一位，同时 更新左边看到的柱子的最高高度 。
     *
     * 同理，我们看情况 2。
     *
     * 情况 2：左边已经看到的最高高度 > 右边已经看到的最高高度。
     *
     * 左边和右边已经看到的最高高度只有 11 个，此时左边虽然还没有扫描，但是下标位置 len - 2 的存水格子数可以确定。它等于：右边已经看到的最高高度 - 当前自己的柱子的高度（大于 00 时有效）。
     *
     * 因为即使中间还有一大片没有扫，根据桶原理，有最左边的柱子存在，中间的柱子或者达到最高，或者中间的柱子都不存在，都不会影响到位置 len - 2 的存水量。
     *
     * 接下来，由于位置 len - 2 确定了，可以把 right 向左移动一位，同时更新右边看到的柱子的最高高度。
     *
     * 至于两边高度相等的情况，归到上面其中一类即可。
     *
     * 在遍历的过程中，由于 left 和 right 向中间靠拢，每移动一个位置，都能确定一个位置的存水格子数，直至相遇，就计算出了全部的存水量。
     *
     * 复杂度分析：
     *
     * 时间复杂度：O(N)O(N)，扫描了 11 次数组；
     * 空间复杂度：O(1)O(1)，只使用了有限个变量。
     * 总结：通过这一道例题，我们再一次看到了「双指针」的应用。我们利用了这道题的特点，结合木桶原理，使用「双指针」相向而行的方式避免了重复扫描区间，减少了计算量，也节约了空间。
     *
     * 作者：liweiwei1419
     * 链接：https://leetcode-cn.com/leetbook/read/learning-algorithms-with-leetcode/x18bji/
     * @param height
     * @return
     */
    public int trap(int[] height) {
        if(height.length==0){
            return 0;
        }
        int left =0,right=height.length-1;
        int ans = 0;
        int leftMax = height[0],rightMax=height[height.length-1];

        while(left<right){
            if(leftMax<rightMax){
                left++;
                if(leftMax>height[left]){
                    ans+=leftMax-height[left];
                }
                leftMax=Math.max(leftMax,height[left]);
            }else{
                right--;
                if(rightMax>height[right]){
                    ans+=rightMax-height[right];
                }
                rightMax=Math.max(rightMax,height[right]);
            }
        }
        return ans;
    }

    /**
     * 方法三：双指针
     * 动态规划的做法中，需要维护两个数组 \textit{leftMax}leftMax 和 \textit{rightMax}rightMax，因此空间复杂度是 O(n)O(n)。是否可以将空间复杂度降到 O(1)O(1)？
     *
     * 注意到下标 ii 处能接的水的量由 \textit{leftMax}[i]leftMax[i] 和 \textit{rightMax}[i]rightMax[i] 中的最小值决定。由于数组 \textit{leftMax}leftMax 是从左往右计算，数组 \textit{rightMax}rightMax 是从右往左计算，因此可以使用双指针和两个变量代替两个数组。
     *
     * 维护两个指针 \textit{left}left 和 \textit{right}right，以及两个变量 \textit{leftMax}leftMax 和 \textit{rightMax}rightMax，初始时 \textit{left}=0,\textit{right}=n-1,\textit{leftMax}=0,\textit{rightMax}=0left=0,right=n−1,leftMax=0,rightMax=0。指针 \textit{left}left 只会向右移动，指针 \textit{right}right 只会向左移动，在移动指针的过程中维护两个变量 \textit{leftMax}leftMax 和 \textit{rightMax}rightMax 的值。
     *
     * 当两个指针没有相遇时，进行如下操作：
     *
     * 使用 \textit{height}[\textit{left}]height[left] 和 \textit{height}[\textit{right}]height[right] 的值更新 \textit{leftMax}leftMax 和 \textit{rightMax}rightMax 的值；
     *
     * 如果 \textit{height}[\textit{left}]<\textit{height}[\textit{right}]height[left]<height[right]，则必有 \textit{leftMax}<\textit{rightMax}leftMax<rightMax，下标 \textit{left}left 处能接的水的量等于 \textit{leftMax}-\textit{height}[\textit{left}]leftMax−height[left]，将下标 \textit{left}left 处能接的水的量加到能接的水的总量，然后将 \textit{left}left 加 11（即向右移动一位）；
     *
     * 如果 \textit{height}[\textit{left}] \ge \textit{height}[\textit{right}]height[left]≥height[right]，则必有 \textit{leftMax} \ge \textit{rightMax}leftMax≥rightMax，下标 \textit{right}right 处能接的水的量等于 \textit{rightMax}-\textit{height}[\textit{right}]rightMax−height[right]，将下标 \textit{right}right 处能接的水的量加到能接的水的总量，然后将 \textit{right}right 减 11（即向左移动一位）。
     *
     * 当两个指针相遇时，即可得到能接的水的总量。
     * 复杂度分析
     *
     * 时间复杂度：O(n)O(n)，其中 nn 是数组 \textit{height}height 的长度。两个指针的移动总次数不超过 nn。
     *
     * 空间复杂度：O(1)O(1)。只需要使用常数的额外空间。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/volume-of-histogram-lcci/solution/zhi-fang-tu-de-shui-liang-by-leetcode-so-7rla/
     * @param height
     * @return
     */
    public int trap_3(int[] height) {
        int n = height.length;
        if(n<3){
            return 0;
        }
        int leftMax=height[0];
        int rightMax=height[n-1];

        int ans=0;
        int left=0,right=n-1;
        while(left<right){
            if(height[left]<=height[right]){
                left++;
                if(left<right&&leftMax>height[left]){
                    ans+=leftMax-height[left];
                }else{
                    leftMax =  height[left];
                }
            }else{
                right--;
                if(right>left&&rightMax>height[right]){
                    ans+=rightMax-height[right];
                }else{
                    rightMax = height[right];
                }
            }

        }
        return ans;
    }

    /**
     * 方法一：动态规划
     * 对于下标 ii，水能到达的最大高度等于下标 ii 两边的最大高度的最小值，下标 ii 处能接的水的量等于下标 ii 处的水能到达的最大高度减去 \textit{height}[i]height[i]。
     *
     * 朴素的做法是对于数组 \textit{height}height 中的每个元素，分别向左和向右扫描并记录左边和右边的最大高度，然后计算每个下标位置能接的水的量。假设数组 \textit{height}height 的长度为 nn，该做法需要对每个下标位置使用 O(n)O(n) 的时间向两边扫描并得到最大高度，因此总时间复杂度是 O(n^2)O(n
     * 2
     *  )。
     *
     * 上述做法的时间复杂度较高是因为需要对每个下标位置都向两边扫描。如果已经知道每个位置两边的最大高度，则可以在 O(n)O(n) 的时间内得到能接的水的总量。使用动态规划的方法，可以在 O(n)O(n) 的时间内预处理得到每个位置两边的最大高度。
     *
     * 创建两个长度为 nn 的数组 \textit{leftMax}leftMax 和 \textit{rightMax}rightMax。对于 0 \le i<n0≤i<n，\textit{leftMax}[i]leftMax[i] 表示下标 ii 及其左边的位置中，\textit{height}height 的最大高度，\textit{rightMax}[i]rightMax[i] 表示下标 ii 及其右边的位置中，\textit{height}height 的最大高度。
     *
     * 显然，\textit{leftMax}[0]=\textit{height}[0]leftMax[0]=height[0]，\textit{rightMax}[n-1]=\textit{height}[n-1]rightMax[n−1]=height[n−1]。两个数组的其余元素的计算如下：
     *
     * 当 1 \le i \le n-11≤i≤n−1 时，\textit{leftMax}[i]=\max(\textit{leftMax}[i-1], \textit{height}[i])leftMax[i]=max(leftMax[i−1],height[i])；
     *
     * 当 0 \le i \le n-20≤i≤n−2 时，\textit{rightMax}[i]=\max(\textit{rightMax}[i+1], \textit{height}[i])rightMax[i]=max(rightMax[i+1],height[i])。
     *
     * 因此可以正向遍历数组 \textit{height}height 得到数组 \textit{leftMax}leftMax 的每个元素值，反向遍历数组 \textit{height}height 得到数组 \textit{rightMax}rightMax 的每个元素值。
     *
     * 在得到数组 \textit{leftMax}leftMax 和 \textit{rightMax}rightMax 的每个元素值之后，对于 0 \le i<n0≤i<n，下标 ii 处能接的水的量等于 \min(\textit{leftMax}[i],\textit{rightMax}[i])-\textit{height}[i]min(leftMax[i],rightMax[i])−height[i]。遍历每个下标位置即可得到能接的水的总量。
     *
     * 动态规划做法可以由下图体现。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/volume-of-histogram-lcci/solution/zhi-fang-tu-de-shui-liang-by-leetcode-so-7rla/
     * 复杂度分析
     *
     * 时间复杂度：O(n)O(n)，其中 nn 是数组 \textit{height}height 的长度。计算数组 \textit{leftMax}leftMax 和 \textit{rightMax}rightMax 的元素值各需要遍历数组 \textit{height}height 一次，计算能接的水的总量还需要遍历一次。
     *
     * 空间复杂度：O(n)O(n)，其中 nn 是数组 \textit{height}height 的长度。需要创建两个长度为 nn 的数组 \textit{leftMax}leftMax 和 \textit{rightMax}rightMax。
     *
     *
     * 方法二：针对暴力解法用空间换时间
     * 开辟两个和原始数组同等长度的数组，扫描两次数组：
     *
     * 从左边向右边扫描：记录当前位置左边的所有柱形的最高高度；
     * 从右边向左边扫描：记录当前位置右边的所有柱形的最高高度。
     * 在扫描的过程中，每一格位置的更新时间复杂度为 O(1)O(1)。最后再扫描一次数组区间 [1, len - 2] ，针对每一格查询上面两个数组，计算出每个格子能够储存雨水的单位。
     *
     * 复杂度分析：
     *
     * 时间复杂度：O(N)O(N)，扫描 33 次数组；
     * 空间复杂度：O(N)O(N)，使用了两个和原始数组同等长度的数组。
     * 事实上，根据这个问题的物理性质，还有更巧妙的办法，只扫描数组 11 次就能计算出结果。
     *
     * 作者：liweiwei1419
     * 链接：https://leetcode-cn.com/leetbook/read/learning-algorithms-with-leetcode/x18bji/
     * @param height
     * @return
     */
    public int trap_2(int[] height) {
        int n = height.length;
        if (n < 3) {
            return 0;
        }

        int[] leftMax = new int[n];
        int[] rightMax = new int[n];

        leftMax[0] = height[0];
        for (int i = 1; i < n; i++) {
            //
            leftMax[i]=Math.max(leftMax[i-1],height[i-1]);
        }
        rightMax[n-1] = height[n-1];
        for (int i = n-2; i >= 0; i--) {
            //
            rightMax[i]= Math.max(rightMax[i+1],height[i+1]);
        }

        int ans=0;
        for (int i = 1; i < n-1; i++) {
            int min = Math.min(leftMax[i], rightMax[i]);
            if (min>height[i]){
                ans+=min-height[i];
            }
        }
        return ans;
    }
}
